package avltree;

public class AVLTree {
    static class TreeNode {
        public int val;
        public int bf; // 平衡因子
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root; // 根节点

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);;
        if (root == null) {
            root = node;
            return true;
        }

        TreeNode parent = root;
        TreeNode cur = null;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        // cur == null
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        node.parent = parent;
        cur = node;
        // 调节平衡因子
        while () {
            // 先看 cur 是 parent 的左树还是右树  决定平衡因子 -- 还是 ++
            if (cur == parent.right) {
                parent.bf++;
            } else {
                parent.bf--;
            }

            if (parent.bf == 0) {
                // 说明已经平衡
                break;
            } else if(parent.bf == 1 || parent.bf == -1) {
                // 继续向上判断, 修改平衡因子
                cur = parent;
                parent = cur.parent;
            } else {
                if (parent.bf == 2) {// 又树高，需要降低又树的高度
                    if (cur.bf == 1) {

                    } else {

                    }
                } else {// 左树高，需要降低左树的高度
                    if (cur.bf == -1) {

                    } else {

                    }
                }
            }

        }


    }

}
